﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 최소전역트리문제
    /// O(E * logV)
    /// </summary>
    class Kruska
    {
        Edge[] es;
        int vCount, eCount;
        public Kruska(Edge[] es, int vCount, int eCount)
        {
            this.es = es;
            this.vCount = vCount;
            this.eCount = eCount;
        }
        public int MinCost()
        {
            es = es.OrderBy(e => e.Cost).ToArray();
            UnionFindTree u = new UnionFindTree(vCount + 1);
            int res = 0;
            for (int i = 0; i < eCount; i++)
            {
                Edge e = es[i];
                if (!u.Same(e.From, e.To))
                {
                    u.Unite(e.From, e.To);
                    Console.Write(e.From + " " + e.To + " (" + e.Cost + ") ");
                    res += e.Cost;
                }
            }
            return res;
        }
    }
}
